package 数据结构和算法入门计划8月开始;

public class 最大子序和0815 {
    //贪心法
    class Solution {// https://leetcode-cn.com/problems/maximum-subarray/solution/tan-xin-chuang-kou-by-bigbeats-5ujy/
        public int maxSubArray(int[] nums) {
            int max = Integer.MIN_VALUE;
            int temp = 0;
            for(int i : nums){
                if(temp + i > 0){
                    temp += i;
                    max = Math.max(max,temp);
                }else if(temp + i <= 0){
                    temp = 0;
                    max = Math.max(i,max);
                }
            }
            return max;
        }
    }

    //动态规划 https://leetcode-cn.com/problems/maximum-subarray/solution/zui-da-zi-xu-he-by-leetcode-solution/
    class Solution1 {
        public int maxSubArray(int[] nums) {
            int pre = 0, maxAns = nums[0];
            for (int x : nums) {
                pre = Math.max(pre + x, x);
                maxAns = Math.max(maxAns, pre);
            }
            return maxAns;
        }
    }
    //动态规划
    class Solution2 { //https://leetcode-cn.com/problems/maximum-subarray/solution/hua-jie-suan-fa-53-zui-da-zi-xu-he-by-guanpengchn/
        public int maxSubArray(int[] nums) {
            int ans = nums[0];
            int sum = 0;
            for(int num: nums) {
                if(sum > 0) {
                    sum += num;
                } else {
                    sum = num;
                }
                ans = Math.max(ans, sum);
            }
            return ans;
        }
    }


}
